package com.xuwei.base.sort;
/**
 * 希尔排序（又称“缩小增量排序”）
 * @author David
 *
 */
public class ShellSort{
    /**
     * @param r      数据元素数组r
     * @param low    数组r的待排序区间[low，high]
     * @param high   
     * @param delta  步长序列delta
     */
	public void shellSort(int[]r,int low,int high,int[] delta){
		for(int k=0;k<delta.length;k++){
			//一趟步长为delta[k]的直接插入排序
			shellInsert(r,low,high,delta[k]);
		}
	}
		
	
	private void shellInsert(int[] r, int low, int high, int deltaK) {
		for(int i=low+deltaK;i<=high;i++){
			if(ShellSort.compare(r[i], r[i-deltaK])<0){
				int temp=r[i];
				int j=i-deltaK;
				for(;j>=low&&ShellSort.compare(temp,r[j])<0;j=j-deltaK){
					r[j+deltaK]=r[j];  //记录后移
				}
				r[j+deltaK]=temp;     //插入到正确的位置
			}  
		}
	}


	public static int compare(int obj1, int obj2) {
		if(obj1<obj2){
			return -1;
		}else if(obj1==obj2){
			return 0;
		}else{
			return 1;
		}
	}	
	
	public static void main(String args[]){
		//待排序的数组
		int r[]={26,53,67,48,57,13,48,32,60,50};
		//排序前
		for(int i=0;i<r.length;i++){
			System.out.print(r[i]+"--");
		}
		System.out.println();
		//步长序列
		int delta[]={5,3,1};
		
		new ShellSort().shellSort(r, 0, 9, delta);
		
		//排序后
		for(int i=0;i<r.length;i++){
			System.out.print(r[i]+"--");
		}
		
	}
	
}
